package SGGStu.QuickSort;

/**
 * @Author：KoVaVo
 * @Version：1.0.0
 * @Description：快速排序
 *
 * 优点：既不浪费空间，又快速的排序
 *
 * 假设对以下几个数字进行快速排序
 * 6 1 2 7 9 3 4 5 10 8
 *
 * 要排序成 1 2 3 4 5 6 7 8 9 10
 * 分析：在初始状态下数字是6开头的，
 * 从右往左找一个比6小的
 * 从左往右找一个比6大的
 * 然后进行位置的交换
 */
public class QuickSort {

    /**
     *
     * @param array
     * @param low
     * @param high
     */
    public static  void  quickSort(int [] array,int low,int high){

        int i,j,temp,t;

        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准单位
        temp=array[low];
        while (i<j){
            //先看右边，从右往左依次递减
            while (temp<=array[j] && i<j){
                j--;
            }
            //在看左边，从左往右一次递增
            while (temp>=array[i] && i<j){
                i++;
            }
            //如果满足条件那么交换
            if(i<j){
                t=array[j];
                array[j]=array[i];
                array[i]=t;
            }
        }

        array[low]=array[i];
        array[i]=temp;
        //递归调用左半数组
        quickSort(array,low,j-1);
        //递归调用右半数组
        quickSort(array,j+1,high);
    }

    public static void main(String[] args) {
        int array [] ={3,2,5,6,4,7,8,0};
        quickSort(array,0,array.length-1);
        System.out.println("===");
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]);
        }
        int l = 0;
        int r = 3;
        System.out.println( l + (int) (Math.random() * (r - l + 1)));
        System.out.println(Math.random());
    }
}
